Chokudai SpeedRun 002 K 種類数β
問題をグラフに帰着する. 具体的には辺$ iが頂点$ A_iと$ B_iをつないでいる辺数$ Nのグラフを考える.
「選ばれる」というのを有向辺の向きで表す. 具体的には入次数が1以上なら選ばれるということにする.
考察すると連結成分ごとに独立であることがわかる.
木の場合, 根以外はすべて入次数を1以上にできるので答えは$ N - 1となる.
木以外の場合, 連結成分ごとに考えるので連結である. 連結ならば全域木が作れることを利用する. すると, 含まれない辺が1つ以上できる. これより答えは$ Nとなる. よって, 木であるかどうかで場合分けしてもよいし, min(頂点数, 辺数)を求め足し合わせて求めてもよいことがわかる.
連結成分ごとの頂点数, 辺数はUnion-Findを用いることで高速に求めることができる.
頂点番号が大きいので(暗に)座標圧縮しなければならないことに注意.